package baoliDigui;

//青蛙跳台阶问题  给定n个台阶  青蛙每次可以跳1个或者两个 请问有多少种跳法
public class TaiJie {
    public static void main(String[] args) {
        System.out.println(getSumWithDP(10));
    }

    //暴力递归
    public static int getSum(int n){
        if (n==1 || n==2){
            return n;
        }
        return getSum(n-1)+getSum(n-2);
    }

    //改dp
    public static int getSumWithDP(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int a=0;a<=n;a++){
            if (a==0 || a==1 || a==2){
                dp[a] = a;
                continue;
            }
            dp[a] = dp[a-1]+dp[a-2];
        }
        return dp[n];
    }
}
